A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
This application includes a computer program listing appendix on a single compact disc, the contents of which are herein incorporated by reference. The compact disc contains a single 318KB file entitled 09-394340, created on Nov. 9, 2001.
The field of the present invention relates to data reading devices and, in particular, to optical code scanners or other label scanning and decoding systems of the type that are designed to read labels having information which may be presented in any one of a number of different codes commonly in use. More particularly, it relates to a system and methodologies for reconstructing complete bar code label information from partial scan information obtained under of variety of non-ideal situations.
Existing labels encode information in a variety of formats and are commonly employed in applications such as inventory control systems and, most familiarly, affixed to consumer goods for retail store check-out, among others. Typically, the information encoded on each label uniquely identifies the product or product line. Such information, once decoded, can be used to identify other information, e.g., price, associated with the labeled object.
Optical scanning systems use various apparatus and methods for the purpose of reading such labels, identifying the particular label format, and decoding the information stored in the label. In the case of bar code scanners, for example, a typical system has one or more light sources, such as a laser or laser diode, which are used to scan the label. Traditional labels are ordinarily composed of a series of parallel dark and light areas, e.g., bars and spaces. A collection subsystem detects at least a portion of the light reflected from the label, distinguishes between dark and light areas, and converts the optical information into an electrical signal that can be recognized by a computer or other electronic system.
Labels, e.g., bar codes or other such symbols, commonly include characters (which can, e.g., be alphanumeric) defined by a number of elements, e.g., bars and spaces. For any given symbology, individual characters within a label are comprised of a given number of elements, and the width of each of these elements is expected to be within a known range, thus allowing the character to be reliably decoded. Exemplary of this is the Universal Product Code (UPC) label in which each character is made up of two bars and two interleaved spaces. The width of each character is measured in units called xe2x80x9cmodulesxe2x80x9d with each character being seven modules in width. The width of any particular bar or space within the character representation is between one and four modules. The character value depends on the relative width in modules of the two bars and two spaces it comprises. For example, indicating bars with a 1 and spaces with a 0, a sequence of 111 would represent a bar that is three modules in width.
If either of the above characteristics is violated (i.e., number of elements per character and/or width of elements in known range), typically the character in question will be considered to be undecodable and the entire scan of data will be discarded. Factors that could cause this are: if an individual element has been split into multiple pieces; multiple elements have been merged into a single piece; or, if the width of an element has been distorted beyond specified boundaries. In any of these instances, some existing systems may require a new scanxe2x80x94discarding the entire scan as unusablexe2x80x94even though only one character may be affected by the degradation.
Some codes make use of parity formats to form alternative representations for the digits 0 through 9. These alternate formats may be utilized in different locations on a label thus providing means for verifying accuracy of data. For example, UPC labels, with the exception of UPC-E labels, are comprised of right and left segment halves. Characters in the left segment are of odd parity and, when scanned from left to right, all begin with spaces. Characters in the right segment are of even parity and, when scanned from left to right, all begin with bars. Thus, the character value 5 may be represented as 0110001 using odd parity or 1001110 using even parity. Likewise, the character 3 may be represented as 0111101 using odd parity or 1000010 using even parity.
Additionally, many labels utilize feature characters, such as center or guard characters, as delimiters or to separate segments of the label. Most UPC labels, as noted above, have left and right segment halves. These segment halves are separated by a center band character that typically comprises two single module bars and three interleaved single module spaces. The beginning and end of the label are delimited by a pair of guard characters, each of which typically comprises two single module bars and one interleaved, single module space. The bar/space representations of these feature characters are unique from that of data characters to enhance detection and decoding capability. Furthermore, an unprinted margin area or white space is typically located outwardly of the two guard characters.
In addition to the UPC formats, a variety of other label formats exist which vary, among other ways, in structure, content, parity requirements, and type of feature characters. Code 39 and Code 128, for example, are both non-segmented label formats, i.e., they have no center feature characters separating two or more segments of bars. Other label encoding schemes have been developed which have differing pattern structures for the dark and light areas. Exemplary of these latter code types are the stacked bar code formats referred to as Code 49 and PDF 417.
As a practical matter, recovering information from optical code labels poses many difficulties that must be overcome by a scanning system. For example, in order to read a label completely, i.e., from left guard character or margin to right guard character or margin, in a single optical pass, the label must be properly oriented with respect to the scanning beam. Failure to read in a single pass, e.g., when a label is mis-framed or read diagonally across a top or bottom border, results in the reading of incomplete or degraded character data and yields partial scans of the label which must be assembled properly in order to formulate valid label information, otherwise the object must be re-positioned and re-scanned until a successful read is obtained. In such cases, data on either end of an input string may be inaccurately read, yet may appear to be an otherwise structurally valid character.
Even where a single optical pass does traverse the entire label from left to right, problems in decoding the label may occur, for example, when the label is folded, split, torn or similarly damaged, thus making it difficult to recover label information. Likewise, differences in package configurations, label sizes and locations, and scanner positions, among other factors, serve to exacerbate these problems. As a result, partially read labels are both more likely to occur and more difficult to decipher. In many applications, such as store check-out stands, this translates to a need for high operator concentration and dexterity yet results in non-optimum speed or efficiency, since the operator must take care to ensure that the object to be scanned is properly positioned (or must reposition and rescan repeatedly for a valid reading). As well, the multitude of optical code formats currently in use may require differing methodologies to be used in order to realize ideal (i.e., optimum speed and efficiency) decoding. In settings where multiple formats may be encountered by the same operator, additional effort and skill may be required to ensure that the system is set for the ideal decoding methodology to be utilized for a particular symbology.
Certain methods of assembling or concatenating data read on partial scans have been proposed to address these difficulties. However, existing methods are inherently limited in their ability to detect and correct for inaccurate and, particularly, missing data reads within partial scans. As well, to the extent that some existing systems have devised more aggressive methods of decoding poor quality or damaged labels, such methods are typically employed at the expense of speed and efficiency in processing good quality, clean labels.
To address the above and many other problems that may be encountered in order to accurately decode a bar code label, the present system provides for a variety of complementary reconstruction methodologies that may be selectively and systematically employed. Aside from known standard decoding algorithms which provide for direct decoding of clean label information obtained from a single scan, the system and method of the preferred embodiment further provides for implementation of known stitching techniques to combine multiple partial scan fragments into complete labels.
In addition, the system provides novel reconstruction methods, which are capable of reconstructing label information such as undecodable characters or elements where label defects may otherwise prevent full information from being decoded. Such reconstruction methods allow for undecodable characters or elements to be reconstructed from partial information based upon known or expected structural characteristics for the particular label symbologies being decoded, as well as through the use of correlation techniques utilizing information obtained from multiple scans of a label. As well, the preferred embodiment offers stitching techniques at the character and element level to aid in the reconstruction of label information.
A means of providing for correction of information at the leading and trailing ends of a label, which might otherwise be distorted and unreadable due to mechanical aspects of the scanning line mechanism, is further provided in a preferred embodiment herein to assist in obtaining complete label information in an efficient and accurate manner. In conjunction with such system and methods as indicated above, the preferred embodiment further provides unique features, such as the use of edge strength indicators and quality measures to enhance label readability and bar code scanner decoding capabilities.
In another aspect, a preferred embodiment herein provides for systematic selection of the decoding techniques to be employed in the process of decoding particular label symbologies. To this end, any number of differently aggressive decoding techniques may be selected, either manually or automatically, to decode label symbologies.
A preferred embodiment provides for decoding of a digital representation of an input signal to be attempted at first with decoding of the part or all of the analog signal being undertaken only after a number of attempts at the digital signal prove unsuccessful. In this manner, system resources and decoding time may be saved.
The type of decoding techniques to be employed may also be set, for example, based on aggressiveness, in a preferred embodiment. In one approach, the system may be set up to attempt less aggressive, more secure, techniques (such as standard decoding techniques) first with more aggressive, less secure techniques (such as character/element reconstruction) being implemented sequentially and systematically should a label fail to be successfully decoded after a number of attempts with less aggressive techniques. Alternatively, beginning and/or ending aggressiveness level to be used may be set, by the user or otherwise, based upon the symbology to be read.
In another approach, the system may be programmed as to aggressiveness levels to be used. In this regard, a starting aggressiveness level and/or maximum aggressiveness level, or both may be programmed. It is envisioned that such programming may, e.g., be based upon user entry by of information regarding the symbology to be read.
In yet another approach, the system may be programmed to learn the aggressiveness level (e.g., starting level, maximum level, or both) to be utilized with respect to a particular group of labels. Such learning may be accomplished, for example, through scanning of an exemplary label with the scanner set in a learning mode whereby the system may assess the appropriate level of aggressiveness required to successfully decode labels of that type. As an alternative to a discrete learning mode, an ongoing learning mode approach may be implemented whereby information about the aggressiveness levels needed to decode would be constantly accumulated as the scanner operates. In accordance with such latter approach, the scanner would adjust itself automatically as label quality changed.
In a still further aspect of the present system and methods, feedback from decoding may also be used to adapt various signal processing parameters. For example, gain, threshold and other signal processing parameters may be automatically adjusted within the scanner based upon feedback from decoding in order to enhance future decodability of label information.
Through the use of the systems and methods detailed herein, the most efficient means of decoding particular labels may be identified and utilized. In turn, less time is required for the decoding process since the time otherwise required to attempt decoding which is not likely to be successful may be eliminated.
Accordingly, the present system and methodologies provide one or more of the following objects and advantages:
to accurately recognize and decode optical labels;
to provide multiple methodologies for reconstructing complete bar code information from partial bar code information obtained from either a single scan or multiple partial scans;
to provide such multiple methodologies for reconstructing complete bar code information in such a manner that the methodologies are implemented in an order from most efficient to less efficient until complete bar code information is obtained;
to provide accurate assembly of label information from multiple partial scans with confidence that the entire label has been scanned, no data has been duplicated, and the data has been put into the correct order;
to have the capability and versatility to reconstruct labels of various formats including multi-block labels as well as single-block labels and others;
to improve reconstruction performance by using symbology characteristics and detected label information to build up labels with a valid high level structure;
to allow a bar code scanner to stitch label fragments that have some undecodable characters present;
to stitch symbologies configured for variable length;
to allow less stringent stitching requirements for fragments that are decoded from consecutive scans compared to fragments that are decoded from non-consecutive scans;
to perform reconstruction of label information in a speedy and efficient manner while alleviating pressure on scanner operator to accurately align the labeled object;
to increase read successes and improve accuracy of reconstruction in situations where label condition is degraded by tears, splits, folds, spots, voids, etc.;
to provide a system and methodologies for decoding labels whereby more aggressive decoding techniques may be implemented only after less aggressive techniques fail; and,
to provide a system and methodologies whereby the appropriate aggressiveness level to be used for decoding particular symbologies may be learned by the system.
Other objects and advantages of the present system and methodologies will become apparent from a review of the accompanying drawings and the detailed description that follows.